package main

import "fmt"

func listSum(arr []int, target int) (i int, j int) {
	counter := 0
	for k, v := range arr {
		for kk, vv := range arr {
			counter++
			if k == kk {
				continue
			}

			if (v + vv) == target {
				fmt.Println("counter:", counter)
				return k, kk
			}
		}
	}
	fmt.Println("counter:", counter)
	return
}

/* 方法一：暴力枚举 */
func twoSumBruteForce(nums []int, target int) []int {
	counter := 0
	size := len(nums)
	// 两层循环，时间复杂度为 O(n^2)
	for i := 0; i < size-1; i++ {
		for j := i + 1; j < size; j++ {
			counter++
			if nums[i]+nums[j] == target {
				fmt.Println("counter:", counter)
				return []int{i, j}
			}
		}
	}

	fmt.Println("counter:", counter)
	return nil
}

/* 方法二：hash表辅助 */
func twoSumHashTable(num []int, target int) (i, j int) {
	uniqueMap := make(map[int]int, len(num))
	for numIdx, v := range num {
		if idx, ok := uniqueMap[target-v]; ok {
			return numIdx, idx
		}
		uniqueMap[v] = numIdx
	}

	return
}
